package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java: 组合总和
public class CombinationSum{
    public static void main(String[] args){
      Solution solution=new CombinationSum().new Solution();
    }
 //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result =new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(result,new ArrayList<>(),candidates,target,0,0);
        return result;
    }

     private void backtracking(List<List<Integer>> result, List<Integer> path, int[] candidates, int target, int sum, int index) {
         if (sum == target) {
             result.add(new ArrayList<>(path));
             return;
         }

         for (int i = index; i < candidates.length; i++) {
             if (sum + candidates[i] > target) break;
             path.add(candidates[i]);
             backtracking(result, path, candidates, target, sum + candidates[i], i);
             path.remove(path.size() - 1);
         }
     }
 }
//leetcode submit region end(Prohibit modification and deletion)

}